SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Division algorithm</title>

</head>

Division algorithm

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">This article is about algorithms for division of integers. For the pencil-and-paper algorithm, see <a href="Long_division" title="Long division">Long division</a>. For the division algorithm for polynomials, see <a href="Polynomial_long_division" title="Polynomial long division">Polynomial long division</a>.</div>

A division algorithm is an <a href="Algorithm" title="Algorithm">algorithm</a> which, given two <a href="Integer" title="Integer">integers</a> N and D (respectively the numerator and the denominator), computes their <a href="Quotient" title="Quotient">quotient</a> and/or <a href="Remainder" title="Remainder">remainder</a>, the result of <a href="Euclidean_division" title="Euclidean division">Euclidean division</a>. Some are applied by hand, while others are employed by digital circuit designs and software.

Division algorithms fall into two main categories: slow division and fast division. Slow division algorithms produce one digit of the final quotient per iteration. Examples of slow division include <a href="#Restoring_division">restoring</a>, non-performing restoring, <a href="#Non-restoring_division">non-restoring</a>, and <a href="#SRT_division">SRT</a> division. Fast division methods start with a close approximation to the final quotient and produce twice as many digits of the final quotient on each iteration.<a href="#cite_note-1">[1]</a> <a href="#Newton–Raphson_division">Newton–Raphson</a> and <a href="#Goldschmidt_division">Goldschmidt</a> algorithms fall into this category.

Variants of these algorithms allow using fast <a href="Multiplication_algorithm" title="Multiplication algorithm">multiplication algorithms</a>. It results that, for large integers, the <a href="Computational_complexity" title="Computational complexity">computer time</a> needed for a division is the same, up to a constant factor, as the time needed for a multiplication, whichever multiplication algorithm is used.

Discussion will refer to the form <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N/D=(Q,R)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N/D=(Q,R)}</annotation>

</semantics>

</math><img src="./7b17784c65376a63bc09d62ba764d95203bea985.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.694ex; height:2.843ex;" alt="{\displaystyle N/D=(Q,R)}" loading="lazy">, where

<ul><li>N = <a href="Fraction" title="Fraction">numerator</a> (dividend)</li>

<li>D = <a href="Fraction" title="Fraction">denominator</a> (divisor)</li></ul>

is the input, and

<ul><li>Q = <a href="Quotient" title="Quotient">quotient</a></li>

<li>R = <a href="Remainder" title="Remainder">remainder</a></li></ul>

is the output.

<div class="mw-heading mw-heading2"><h2 id="Division_by_repeated_subtraction">Division by repeated subtraction</h2></div>

The simplest division algorithm, historically incorporated into a <a href="Greatest_common_divisor" title="Greatest common divisor">greatest common divisor</a> algorithm presented in <a href="Euclid's_Elements" title="Euclid's Elements">Euclid's Elements</a>, Book VII, Proposition 1, finds the remainder given two positive integers using only subtractions and comparisons:

<div class="mw-highlight mw-highlight-lang-lua mw-content-ltr" dir="ltr"><pre>R := N

Q := 0

while R ≥ D do

R := R − D

Q := Q + 1

end

return (Q,R)

</pre></div>

The proof that the quotient and remainder exist and are unique (described at <a href="Euclidean_division" title="Euclidean division">Euclidean division</a>) gives rise to a complete division algorithm, applicable to both negative and positive numbers, using additions, subtractions, and comparisons:

<div class="mw-highlight mw-highlight-lang-lua mw-content-ltr" dir="ltr"><pre>function divide(N, D)

if D = 0 then error(DivisionByZero) end

if D < 0 then (Q, R) := divide(N, −D); return (−Q, R) end

if N < 0 then

(Q,R) := divide(−N, D)

if R = 0 then return (−Q, 0)

else return (−Q − 1, D − R) end

end

-- At this point, N ≥ 0 and D > 0

return divide_unsigned(N, D)

end

function divide_unsigned(N, D)

Q := 0; R := N

while R ≥ D do

Q := Q + 1

R := R − D

end

return (Q, R)

end

</pre></div>

This procedure always produces R ≥ 0. Although very simple, it takes Ω(Q) steps, and so is exponentially slower than even slow division algorithms like long division. It is useful if Q is known to be small (being an <a href="Output-sensitive_algorithm" title="Output-sensitive algorithm">output-sensitive algorithm</a>), and can serve as an executable specification.

<div class="mw-heading mw-heading2"><h2 id="Long_division">Long division</h2></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Long_division#Algorithm_for_arbitrary_base" title="Long division">Long division § Algorithm for arbitrary base</a></div>

Long division is the standard algorithm used for pen-and-paper division of multi-digit numbers expressed in decimal notation. It shifts gradually from the left to the right end of the dividend, subtracting the largest possible multiple of the divisor (at the digit level) at each stage; the multiples then become the digits of the quotient, and the final difference is then the remainder.

When used with a binary radix, this method forms the basis for the (unsigned) integer division with remainder algorithm below. <a href="Short_division" title="Short division">Short division</a> is an abbreviated form of long division suitable for one-digit divisors. <a href="Chunking_(division)" title="Chunking (division)">Chunking</a> – also known as the partial quotients method or the hangman method – is a less-efficient form of long division which may be easier to understand. By allowing one to subtract more multiples than what one currently has at each stage, a more freeform variant of long division can be developed as well.

<div class="mw-heading mw-heading3"><h3 id="Integer_division_(unsigned)_with_remainder">Integer division (unsigned) with remainder</h3></div>

<div role="note" class="hatnote navigation-not-searchable">See also: <a href="Binary_number#Division" title="Binary number">Binary number § Division</a></div>

The following algorithm, the binary version of the famous <a href="Long_division" title="Long division">long division</a>, will divide N by D, placing the quotient in Q and the remainder in R. In the following pseudo-code, all values are treated as unsigned integers.

<div class="mw-highlight mw-highlight-lang-lua mw-content-ltr" dir="ltr"><pre>if D = 0 then error(DivisionByZeroException) end

Q := 0 -- Initialize quotient and remainder to zero

R := 0

for i := n − 1 .. 0 do -- Where n is number of bits in N

R := R << 1 -- Left-shift R by 1 bit

R(0) := N(i) -- Set the least-significant bit of R equal to bit i of the numerator

if R ≥ D then

R := R − D

Q(i) := 1

end

end

</pre></div>

<div class="mw-heading mw-heading4"><h4 id="Example">Example</h4></div>

If we take N=11002 (1210) and D=1002 (410)

Step 1: Set R=0 and Q=0

Step 2: Take i=3 (one less than the number of bits in N)

Step 3: R=00 (left shifted by 1)

Step 4: R=01 (setting R(0) to N(i))

Step 5: R < D, so skip statement

Step 2: Set i=2

Step 3: R=010

Step 4: R=011

Step 5: R < D, statement skipped

Step 2: Set i=1

Step 3: R=0110

Step 4: R=0110

Step 5: R>=D, statement entered

Step 5b: R=10 (R−D)

Step 5c: Q=10 (setting Q(i) to 1)

Step 2: Set i=0

Step 3: R=100

Step 4: R=100

Step 5: R>=D, statement entered

Step 5b: R=0 (R−D)

Step 5c: Q=11 (setting Q(i) to 1)

end

Q=112 (310) and R=0.

<div class="mw-heading mw-heading2"><h2 id="Slow_division_methods">Slow division methods</h2></div>

Slow division methods are all based on a standard recurrence equation<a href="#cite_note-2">[2]</a>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R_{j+1}=B\times R_{j}-q_{n-(j+1)}\times D,}</annotation>

</semantics>

</math><img src="./2061a50ce24d8a03d89503cff51bca6438d0714c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:30.994ex; height:3.009ex;" alt="{\displaystyle R_{j+1}=B\times R_{j}-q_{n-(j+1)}\times D,}" loading="lazy"></dd></dl>

where:

<ul><li>Rj is the j-th partial remainder of the division</li>

<li>B is the <a href="Radix" title="Radix">radix</a> (base, usually 2 internally in computers and calculators)</li>

<li>q n − (j + 1) is the digit of the quotient in position n−(j+1), where the digit positions are numbered from least-significant 0 to most significant n−1</li>

<li>n is number of digits in the quotient</li>

<li>D is the divisor</li></ul>

<div class="mw-heading mw-heading3"><h3 id="Restoring_division">Restoring division</h3></div>

Restoring division operates on <a href="Fixed_point_arithmetic" class="mw-redirect" title="Fixed point arithmetic">fixed-point</a> fractional numbers and depends on the assumption 0 < D < N.

The quotient digits q are formed from the digit set {0,1}.

The basic algorithm for binary (radix 2) restoring division is:

<div class="mw-highlight mw-highlight-lang-lua mw-content-ltr" dir="ltr"><pre>R := N

D := D << n -- R and D need twice the word width of N and Q

for i := n − 1 .. 0 do -- For example 31..0 for 32 bits

R := 2 * R − D -- Trial subtraction from shifted value (multiplication by 2 is a shift in binary representation)

if R >= 0 then

q(i) := 1 -- Result-bit 1

else

q(i) := 0 -- Result-bit 0

R := R + D -- New partial remainder is (restored) shifted value

end

end

-- Where: N = numerator, D = denominator, n = #bits, R = partial remainder, q(i) = bit #i of quotient

</pre></div>

Non-performing restoring division is similar to restoring division except that the value of 2R is saved, so D does not need to be added back in for the case of R < 0.

<div class="mw-heading mw-heading3"><h3 id="Non-restoring_division">Non-restoring division</h3></div>

Non-restoring division uses the digit set {−1, 1} for the quotient digits instead of {0, 1}. The algorithm is more complex, but has the advantage when implemented in hardware that there is only one decision and addition/subtraction per quotient bit; there is no restoring step after the subtraction,<a href="#cite_note-3">[3]</a> which potentially cuts down the numbers of operations by up to half and lets it be executed faster.<a href="#cite_note-4">[4]</a> The basic algorithm for binary (radix 2) non-restoring division of non-negative numbers is:

<div class="mw-highlight mw-highlight-lang-lua mw-content-ltr" dir="ltr"><pre>R := N

D := D << n -- R and D need twice the word width of N and Q

for i = n − 1 .. 0 do -- for example 31..0 for 32 bits

if R >= 0 then

q(i) := +1

R := 2 * R − D

else

q(i) := −1

R := 2 * R + D

end if

end

-- Note: N=numerator, D=denominator, n=#bits, R=partial remainder, q(i)=bit #i of quotient.

</pre></div>

Following this algorithm, the quotient is in a non-standard form consisting of digits of −1 and +1. This form needs to be converted to binary to form the final quotient. Example:

<td colspan="2">Convert the following quotient to the digit set {0,1}:

</td></tr>

<tr>

<td>Start:</td>

<mover>

</mover>

</mrow>

<mover>

</mover>

</mrow>

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Q=111{\bar {1}}1{\bar {1}}1{\bar {1}}}</annotation>

</semantics>

</math><img src="./ff1c6deb0ef9ed263044261ae08c4f75dff7944e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:14.236ex; height:2.843ex;" alt="{\displaystyle Q=111{\bar {1}}1{\bar {1}}1{\bar {1}}}" loading="lazy">

</td></tr>

<tr>

<td>1. Form the positive term:</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P=11101010\,}</annotation>

</semantics>

</math><img src="./00a969b72bea5caf34bc5f673174c1aac75ca10b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:14.531ex; height:2.176ex;" alt="{\displaystyle P=11101010\,}" loading="lazy">

</td></tr>

<tr>

<td>2. Mask the negative term:<a href="#cite_note-5">[note 1]</a></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M=00010101\,}</annotation>

</semantics>

</math><img src="./5e944f1f61ca3ce53751c497b3ddc233d0e24e39.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:15.227ex; height:2.176ex;" alt="{\displaystyle M=00010101\,}" loading="lazy">

</td></tr>

<tr>

<td>3. Subtract: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P-M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P-M}</annotation>

</semantics>

</math><img src="./bc08dd736707753293e96c9cc88f4485bd386d4d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:7.028ex; height:2.343ex;" alt="{\displaystyle P-M}" loading="lazy">:</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Q=11010101\,}</annotation>

</semantics>

</math><img src="./70cada62fee03b73cd8a2e51dec51fb4c7409c02.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:14.624ex; height:2.509ex;" alt="{\displaystyle Q=11010101\,}" loading="lazy">

</td></tr>

<tr>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

<li id="cite_note-5"><a href="#cite_ref-5">^</a> Signed binary notation with <a href="Ones'_complement" title="Ones' complement">ones' complement</a> without <a href="Two's_complement" title="Two's complement">two's complement</a>.

</li>

</ol></div></div>

</td></tr></tbody></table>

If the −1 digits of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Q}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Q}</annotation>

</semantics>

</math><img src="./8752c7023b4b3286800fe3238271bbca681219ed.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.838ex; height:2.509ex;" alt="{\displaystyle Q}" loading="lazy"> are stored as zeros (0) as is common, then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy"> is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Q}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Q}</annotation>

</semantics>

</math><img src="./8752c7023b4b3286800fe3238271bbca681219ed.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.838ex; height:2.509ex;" alt="{\displaystyle Q}" loading="lazy"> and computing <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"> is trivial: perform a ones' complement (bit by bit complement) on the original <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Q}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Q}</annotation>

</semantics>

</math><img src="./8752c7023b4b3286800fe3238271bbca681219ed.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.838ex; height:2.509ex;" alt="{\displaystyle Q}" loading="lazy">.

<div class="mw-highlight mw-highlight-lang-lua mw-content-ltr" dir="ltr"><pre>Q := Q − bit.bnot(Q) -- Appropriate if −1 digits in Q are represented as zeros as is common.

</pre></div>

Finally, quotients computed by this algorithm are always odd, and the remainder in R is in the range −D ≤ R < D. For example, 5 / 2 = 3 R −1. To convert to a positive remainder, do a single restoring step after Q is converted from non-standard form to standard form:

<div class="mw-highlight mw-highlight-lang-lua mw-content-ltr" dir="ltr"><pre>if R < 0 then

Q := Q − 1

R := R + D -- Needed only if the remainder is of interest.

end if

</pre></div>

The actual remainder is R >> n. (As with restoring division, the low-order bits of R are used up at the same rate as bits of the quotient Q are produced, and it is common to use a single shift register for both.)

<div class="mw-heading mw-heading3"><h3 id="SRT_division">SRT division</h3></div>

SRT division is a popular method for division in many <a href="Microprocessor" title="Microprocessor">microprocessor</a> implementations.<a href="#cite_note-6">[5]</a><a href="#cite_note-7">[6]</a> The algorithm is named after D. W. Sweeney of <a href="IBM" title="IBM">IBM</a>, James E. Robertson of <a href="University_of_Illinois" class="mw-redirect" title="University of Illinois">University of Illinois</a>, and <a href="K._D._Tocher" title="K. D. Tocher">K. D. Tocher</a> of <a href="Imperial_College_London" title="Imperial College London">Imperial College London</a>. They all developed the algorithm independently at approximately the same time (published in February 1957, September 1958, and January 1958 respectively).<a href="#cite_note-8">[7]</a><a href="#cite_note-9">[8]</a><a href="#cite_note-10">[9]</a>

SRT division is similar to non-restoring division, but it uses a <a href="Lookup_table" title="Lookup table">lookup table</a> based on the dividend and the divisor to determine each quotient digit.

The most significant difference is that a redundant representation is used for the quotient. For example, when implementing radix-4 SRT division, each quotient digit is chosen from five possibilities: { −2, −1, 0, +1, +2 }. Because of this, the choice of a quotient digit need not be perfect; later quotient digits can correct for slight errors. (For example, the quotient digit pairs (0, +2) and (1, −2) are equivalent, since 0×4+2 = 1×4−2.) This tolerance allows quotient digits to be selected using only a few most-significant bits of the dividend and divisor, rather than requiring a full-width subtraction. This simplification in turn allows a radix higher than 2 to be used.

Like non-restoring division, the final steps are a final full-width subtraction to resolve the last quotient bit, and conversion of the quotient to standard binary form.

The <a href="Original_Intel_Pentium_(P5_microarchitecture)" class="mw-redirect" title="Original Intel Pentium (P5 microarchitecture)">Intel Pentium</a> processor's <a href="Pentium_FDIV_bug" title="Pentium FDIV bug">infamous floating-point division bug</a> was caused by an incorrectly coded lookup table. Five of the 1066 entries had been mistakenly omitted.<a href="#cite_note-11">[10]</a><a href="#cite_note-12">[11]</a><a href="#cite_note-13">[12]</a>

<div class="mw-heading mw-heading2"><h2 id="Fast_division_methods">Fast division methods</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Newton–Raphson_division">Newton–Raphson division</h3></div>

Newton–Raphson uses <a href="Newton's_method" title="Newton's method">Newton's method</a> to find the <a href="Multiplicative_inverse" title="Multiplicative inverse">reciprocal</a> of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D}</annotation>

</semantics>

</math><img src="./f34a0c600395e5d4345287e21fb26efd386990e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.924ex; height:2.176ex;" alt="{\displaystyle D}" loading="lazy"> and multiply that reciprocal by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"> to find the final quotient <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Q}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Q}</annotation>

</semantics>

</math><img src="./8752c7023b4b3286800fe3238271bbca681219ed.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.838ex; height:2.509ex;" alt="{\displaystyle Q}" loading="lazy">.

The steps of Newton–Raphson division are:

<ol><li>Calculate an estimate <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X_{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X_{0}}</annotation>

</semantics>

</math><img src="./6381fdad2b9f11954b1fc2db08bbaccf634ededa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.979ex; height:2.509ex;" alt="{\displaystyle X_{0}}" loading="lazy"> for the reciprocal <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1/D}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1/D}</annotation>

</semantics>

</math><img src="./0ebe16539fe93aaebbd7b4011b3c2ac87fe1b9aa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.249ex; height:2.843ex;" alt="{\displaystyle 1/D}" loading="lazy"> of the divisor <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D}</annotation>

</semantics>

</math><img src="./f34a0c600395e5d4345287e21fb26efd386990e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.924ex; height:2.176ex;" alt="{\displaystyle D}" loading="lazy">.</li>

<li>Compute successively more accurate estimates <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X_{1},X_{2},\ldots ,X_{S}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X_{1},X_{2},\ldots ,X_{S}}</annotation>

</semantics>

</math><img src="./46cf2ec617c833e20a7656b41a2f9168f24a37df.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:15.386ex; height:2.509ex;" alt="{\displaystyle X_{1},X_{2},\ldots ,X_{S}}" loading="lazy"> of the reciprocal. This is where one employs the Newton–Raphson method as such.</li>

<li>Compute the quotient by multiplying the dividend by the reciprocal of the divisor: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Q=NX_{S}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Q=NX_{S}}</annotation>

</semantics>

</math><img src="./cf408f63af6025ec07885817f55a6e73f53f6314.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.217ex; height:2.509ex;" alt="{\displaystyle Q=NX_{S}}" loading="lazy">.</li></ol>

In order to apply Newton's method to find the reciprocal of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D}</annotation>

</semantics>

</math><img src="./f34a0c600395e5d4345287e21fb26efd386990e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.924ex; height:2.176ex;" alt="{\displaystyle D}" loading="lazy">, it is necessary to find a function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(X)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(X)}</annotation>

</semantics>

</math><img src="./b884e2d65b3356219702968b6751485fb8f38570.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.068ex; height:2.843ex;" alt="{\displaystyle f(X)}" loading="lazy"> that has a zero at <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X=1/D}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X=1/D}</annotation>

</semantics>

</math><img src="./5b4dcccbdb6fbe7b3badab65d90fae2a3b67542a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.328ex; height:2.843ex;" alt="{\displaystyle X=1/D}" loading="lazy">. The obvious such function is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(X)=DX-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(X)=DX-1}</annotation>

</semantics>

</math><img src="./6cd146824dc4fa5111538bba41c99ac2da3d55c9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.073ex; height:2.843ex;" alt="{\displaystyle f(X)=DX-1}" loading="lazy">, but the Newton–Raphson iteration for this is unhelpful, since it cannot be computed without already knowing the reciprocal of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D}</annotation>

</semantics>

</math><img src="./f34a0c600395e5d4345287e21fb26efd386990e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.924ex; height:2.176ex;" alt="{\displaystyle D}" loading="lazy"> (moreover it attempts to compute the exact reciprocal in one step, rather than allow for iterative improvements). A function that does work is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(X)=(1/X)-D}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(X)=(1/X)-D}</annotation>

</semantics>

</math><img src="./ed1147f5c4854b44d324c4b83238ea2cdb479b84.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.045ex; height:2.843ex;" alt="{\displaystyle f(X)=(1/X)-D}" loading="lazy">, for which the Newton–Raphson iteration gives

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

<mrow>

<msup>

</msup>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

<mrow>

</mrow>

</mrow>

</mrow>

</msubsup>

</mrow>

</mfrac>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X_{i+1}=X_{i}-{f(X_{i}) \over f'(X_{i})}=X_{i}-{1/X_{i}-D \over -1/X_{i}^{2}}=X_{i}+X_{i}(1-DX_{i})=X_{i}(2-DX_{i}),}</annotation>

</semantics>

</math></dd></dl>

which can be calculated from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X_{i}}</annotation>

</semantics>

</math><img src="./af4a0955af42beb5f85aa05fb8c07abedc13990d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.724ex; height:2.509ex;" alt="{\displaystyle X_{i}}" loading="lazy"> using only multiplication and subtraction, or using two <a href="Fused_multiply%E2%80%93add" class="mw-redirect" title="Fused multiply–add">fused multiply–adds</a>.

From a computation point of view, the expressions <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X_{i+1}=X_{i}+X_{i}(1-DX_{i})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X_{i+1}=X_{i}+X_{i}(1-DX_{i})}</annotation>

</semantics>

</math><img src="./c177500ed6b2494d92b3e2c9146071163f5c340b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:26.672ex; height:2.843ex;" alt="{\displaystyle X_{i+1}=X_{i}+X_{i}(1-DX_{i})}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X_{i+1}=X_{i}(2-DX_{i})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X_{i+1}=X_{i}(2-DX_{i})}</annotation>

</semantics>

</math><img src="./e69468a89d244eca202bc454f97554803b997d41.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.107ex; height:2.843ex;" alt="{\displaystyle X_{i+1}=X_{i}(2-DX_{i})}" loading="lazy"> are not equivalent. To obtain a result with a precision of 2n bits while making use of the second expression, one must compute the product between <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X_{i}}</annotation>

</semantics>

</math><img src="./af4a0955af42beb5f85aa05fb8c07abedc13990d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.724ex; height:2.509ex;" alt="{\displaystyle X_{i}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (2-DX_{i})}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (2-DX_{i})}</annotation>

</semantics>

</math><img src="./ff857ba14b90566446aad8257ebae460ca851674.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.46ex; height:2.843ex;" alt="{\displaystyle (2-DX_{i})}" loading="lazy"> with double the given precision of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X_{i}}</annotation>

</semantics>

</math><img src="./af4a0955af42beb5f85aa05fb8c07abedc13990d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.724ex; height:2.509ex;" alt="{\displaystyle X_{i}}" loading="lazy">(n bits). In contrast, the product between <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X_{i}}</annotation>

</semantics>

</math><img src="./af4a0955af42beb5f85aa05fb8c07abedc13990d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.724ex; height:2.509ex;" alt="{\displaystyle X_{i}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (1-DX_{i})}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (1-DX_{i})}</annotation>

</semantics>

</math><img src="./0b81a3e0d6031af2c0a8b1aea61d07d8160b9775.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.46ex; height:2.843ex;" alt="{\displaystyle (1-DX_{i})}" loading="lazy"> need only be computed with a precision of n bits, because the leading n bits (after the binary point) of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (1-DX_{i})}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (1-DX_{i})}</annotation>

</semantics>

</math><img src="./0b81a3e0d6031af2c0a8b1aea61d07d8160b9775.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.46ex; height:2.843ex;" alt="{\displaystyle (1-DX_{i})}" loading="lazy"> are zeros.

If the error is defined as <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varepsilon _{i}=1-DX_{i}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varepsilon _{i}=1-DX_{i}}</annotation>

</semantics>

</math><img src="./98115ffa92ddc012d5ca75557304758ab6693ee8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.633ex; height:2.509ex;" alt="{\displaystyle \varepsilon _{i}=1-DX_{i}}" loading="lazy">, then:

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msubsup>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

<msup>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msup>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}\varepsilon _{i+1}&=1-DX_{i+1}\\&=1-D(X_{i}(2-DX_{i}))\\&=1-2DX_{i}+D^{2}X_{i}^{2}\\&=(1-DX_{i})^{2}\\&={\varepsilon _{i}}^{2}.\\\end{aligned}}}</annotation>

</semantics>

</math><img src="./656efcc4fb42843a4eb2dd7b7c03257fd9eaaeb8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -7.505ex; width:28.754ex; height:16.176ex;" alt="{\displaystyle {\begin{aligned}\varepsilon _{i+1}&=1-DX_{i+1}\\&=1-D(X_{i}(2-DX_{i}))\\&=1-2DX_{i}+D^{2}X_{i}^{2}\\&=(1-DX_{i})^{2}\\&={\varepsilon _{i}}^{2}.\\\end{aligned}}}" loading="lazy"></dd></dl>

This squaring of the error at each iteration step – the so-called <a href="Newton's_method#Practical_considerations" title="Newton's method">quadratic convergence</a> of Newton–Raphson's method – has the effect that the number of correct digits in the result roughly doubles for every iteration, a property that becomes extremely valuable when the numbers involved have many digits (e.g. in the large integer domain). But it also means that the initial convergence of the method can be comparatively slow, especially if the initial estimate <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X_{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X_{0}}</annotation>

</semantics>

</math><img src="./6381fdad2b9f11954b1fc2db08bbaccf634ededa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.979ex; height:2.509ex;" alt="{\displaystyle X_{0}}" loading="lazy"> is poorly chosen.

<div class="mw-heading mw-heading4"><h4 id="Initial_estimate">Initial estimate</h4></div>

For the subproblem of choosing an initial estimate <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X_{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X_{0}}</annotation>

</semantics>

</math><img src="./6381fdad2b9f11954b1fc2db08bbaccf634ededa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.979ex; height:2.509ex;" alt="{\displaystyle X_{0}}" loading="lazy">, it is convenient to apply a bit-shift to the divisor D to scale it so that 0.5 ≤ D ≤ 1. Applying the same bit-shift to the numerator N ensures the quotient does not change. Once within a bounded range, a simple polynomial <a href="Approximation" title="Approximation">approximation</a> can be used to find an initial estimate.

The linear <a href="Approximation" title="Approximation">approximation</a> with minimum worst-case absolute error on the interval <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [0.5,1]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [0.5,1]}</annotation>

</semantics>

</math><img src="./28b12b2e130f0013fb23a77854afeb5dafbc0d48.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.462ex; height:2.843ex;" alt="{\displaystyle [0.5,1]}" loading="lazy"> is:

<msub>

</mrow>

</msub>

<mfrac>

</mfrac>

</mrow>

<mfrac>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X_{0}={48 \over 17}-{32 \over 17}D.}</annotation>

</semantics>

</math><img src="./7620ba3247e41c32011a3651d0ddf453aadfc670.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:17.811ex; height:5.343ex;" alt="{\displaystyle X_{0}={48 \over 17}-{32 \over 17}D.}" loading="lazy"></dd></dl>

The coefficients of the linear approximation <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{0}+T_{1}D}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T_{0}+T_{1}D}</annotation>

</semantics>

</math><img src="./0af67cca8981fef89447d1cd19c2389b6e45c5d5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.588ex; height:2.509ex;" alt="{\displaystyle T_{0}+T_{1}D}" loading="lazy"> are determined as follows. The absolute value of the error is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |\varepsilon _{0}|=|1-D(T_{0}+T_{1}D)|}">

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |\varepsilon _{0}|=|1-D(T_{0}+T_{1}D)|}</annotation>

</semantics>

</math><img src="./129dc5f2ff26b8594765bcc95d379967a9fa084c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:25.148ex; height:2.843ex;" alt="{\displaystyle |\varepsilon _{0}|=|1-D(T_{0}+T_{1}D)|}" loading="lazy">. The minimum of the maximum absolute value of the error is determined by the <a href="Equioscillation_theorem" title="Equioscillation theorem">Chebyshev equioscillation theorem</a> applied to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F(D)=1-D(T_{0}+T_{1}D)}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F(D)=1-D(T_{0}+T_{1}D)}</annotation>

</semantics>

</math><img src="./ba6c76c134213c5ac91eac9cb50958498bb832ba.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:25.897ex; height:2.843ex;" alt="{\displaystyle F(D)=1-D(T_{0}+T_{1}D)}" loading="lazy">. The local minimum of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F(D)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F(D)}</annotation>

</semantics>

</math><img src="./7bd590623db38ab20e65c64d9d079cb80025ec5e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.474ex; height:2.843ex;" alt="{\displaystyle F(D)}" loading="lazy"> occurs when <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F'(D)=0}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F'(D)=0}</annotation>

</semantics>

</math><img src="./2989b2fa88989ae10bc24deeb6ca873c69bc73e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.494ex; height:3.009ex;" alt="{\displaystyle F'(D)=0}" loading="lazy">, which has solution <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D=-T_{0}/(2T_{1})}">

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D=-T_{0}/(2T_{1})}</annotation>

</semantics>

</math><img src="./35ecf66df4ba538f63a3c78b59908a97985f24fa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.789ex; height:2.843ex;" alt="{\displaystyle D=-T_{0}/(2T_{1})}" loading="lazy">. The function at that minimum must be of opposite sign as the function at the endpoints, namely, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F(1/2)=F(1)=-F(-T_{0}/(2T_{1}))}">

</mrow>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F(1/2)=F(1)=-F(-T_{0}/(2T_{1}))}</annotation>

</semantics>

</math><img src="./83af1e372bdb0f886a2201530fc6c9968fdeae90.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:34.071ex; height:2.843ex;" alt="{\displaystyle F(1/2)=F(1)=-F(-T_{0}/(2T_{1}))}" loading="lazy">. The two equations in the two unknowns have a unique solution <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{0}=48/17}">

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T_{0}=48/17}</annotation>

</semantics>

</math><img src="./40e3ea5c40cbde77066f42a18c324f73a4965ea9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.323ex; height:2.843ex;" alt="{\displaystyle T_{0}=48/17}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{1}=-32/17}">

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T_{1}=-32/17}</annotation>

</semantics>

</math><img src="./bf9fbc7da2b73d371965dbf0555b941d9674f795.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.131ex; height:2.843ex;" alt="{\displaystyle T_{1}=-32/17}" loading="lazy">, and the maximum error is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F(1)=1/17}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F(1)=1/17}</annotation>

</semantics>

</math><img src="./a7e26e4f69bf106cbbc1c2c535da24e3e24bfca8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.461ex; height:2.843ex;" alt="{\displaystyle F(1)=1/17}" loading="lazy">. Using this approximation, the absolute value of the error of the initial value is less than

<msub>

</mrow>

</msub>

<mfrac>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \vert \varepsilon _{0}\vert \leq {1 \over 17}\approx 0.059.}</annotation>

</semantics>

</math><img src="./a07026fe7ed3e0da53f49760ac667af07fbb6bf9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:18.733ex; height:5.343ex;" alt="{\displaystyle \vert \varepsilon _{0}\vert \leq {1 \over 17}\approx 0.059.}" loading="lazy"></dd></dl>

The best quadratic fit to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1/D}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1/D}</annotation>

</semantics>

</math><img src="./0ebe16539fe93aaebbd7b4011b3c2ac87fe1b9aa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.249ex; height:2.843ex;" alt="{\displaystyle 1/D}" loading="lazy"> in the interval is

<mfrac>

</mfrac>

</mrow>

<mfrac>

</mfrac>

</mrow>

<mfrac>

</mfrac>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X:={\frac {140}{33}}-{\frac {64}{11}}D+{\frac {256}{99}}D^{2}.}</annotation>

</semantics>

</math><img src="./15b8ff1e267881575e73dea0f8620e8a4cef80e9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:28.764ex; height:5.176ex;" alt="{\displaystyle X:={\frac {140}{33}}-{\frac {64}{11}}D+{\frac {256}{99}}D^{2}.}" loading="lazy"></dd></dl>

It is chosen to make the error equal to a re-scaled third order <a href="Chebyshev_polynomial" class="mw-redirect" title="Chebyshev polynomial">Chebyshev polynomial</a> of the first kind, and gives an absolute value of the error less than or equal to 1/99. This improvement is equivalent to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \log _{2}(\log 99/\log 17)\approx 0.7}">

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \log _{2}(\log 99/\log 17)\approx 0.7}</annotation>

</semantics>

</math><img src="./8740f22e9c560fc72461b499617ee7016b1e9bad.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:24.823ex; height:2.843ex;" alt="{\displaystyle \log _{2}(\log 99/\log 17)\approx 0.7}" loading="lazy"> Newton–Raphson iterations, at a computational cost of less than one iteration.

It is possible to generate a polynomial fit of degree larger than 2, computing the coefficients using the <a href="Remez_algorithm" title="Remez algorithm">Remez algorithm</a>. The trade-off is that the initial guess requires more computational cycles but hopefully in exchange for fewer iterations of Newton–Raphson.

Since for this method the <a href="Rate_of_convergence" title="Rate of convergence">convergence</a> is exactly quadratic, it follows that, from an initial error <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varepsilon _{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varepsilon _{0}}</annotation>

</semantics>

</math><img src="./acb0a8377db20e42274444cb181d51b5532b5844.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.138ex; height:2.009ex;" alt="{\displaystyle \varepsilon _{0}}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math><img src="./4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"> iterations will give an answer accurate to

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P=-2^{S}\log _{2}\varepsilon _{0}-1=2^{S}\log _{2}(1/\varepsilon _{0})-1}</annotation>

</semantics>

</math><img src="./7db4bc594a5bf55861facfade05bd551d5c64796.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:40.289ex; height:3.176ex;" alt="{\displaystyle P=-2^{S}\log _{2}\varepsilon _{0}-1=2^{S}\log _{2}(1/\varepsilon _{0})-1}" loading="lazy"></dd></dl>

binary places. Typical values are:

<caption>Binary digits of reciprocal accuracy

</caption>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varepsilon _{0}}</annotation>

</semantics>

</math><img src="./acb0a8377db20e42274444cb181d51b5532b5844.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.138ex; height:2.009ex;" alt="{\displaystyle \varepsilon _{0}}" loading="lazy"></th>

<th colspan="5">Iterations

</th></tr>

<tr>

<th>4

</th></tr>

<tr>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1/17}</annotation>

</semantics>

</math><img src="./fddffd4792f3b4245b41d8f7e551d766cec12bd5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.65ex; height:2.843ex;" alt="{\displaystyle 1/17}" loading="lazy">

</th>

<td>3.09

</td>

<td>7.17

</td>

<td>15.35

</td>

<td>31.70

</td>

<td>64.40

</td></tr>

<tr>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1/99}</annotation>

</semantics>

</math><img src="./450c9c8260e8f5f1f8d21bca139120eac9376ac8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.65ex; height:2.843ex;" alt="{\displaystyle 1/99}" loading="lazy">

</th>

<td>5.63

</td>

<td>12.26

</td>

<td>25.52

</td>

<td>52.03

</td>

<td>105.07

</td></tr></tbody></table>

A quadratic initial estimate plus two iterations is accurate enough for IEEE <a href="Single_precision" class="mw-redirect" title="Single precision">single precision</a>, but three iterations are marginal for <a href="Double_precision" class="mw-redirect" title="Double precision">double precision</a>. A linear initial estimate plus four iterations is sufficient for both double and <a href="Extended_precision" title="Extended precision">double extended</a> formats.

<div class="mw-heading mw-heading4"><h4 id="Pseudocode">Pseudocode</h4></div>

The following computes the quotient of <var style="padding-right: 1px;">N</var> and <var style="padding-right: 1px;">D</var> with a precision of <var style="padding-right: 1px;">P</var> binary places:

Express D as M × 2e where 1 ≤ M < 2 (standard floating point representation)

D' := D / 2e+1 // scale between 0.5 and 1, can be performed with bit shift / exponent subtraction

N' := N / 2e+1

X := 48/17 − 32/17 × D' // precompute constants with same precision as D

repeat <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left\lceil \log _{2}{\frac {P+1}{\log _{2}17}}\right\rceil \,}">

<mrow>

<mrow>

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left\lceil \log _{2}{\frac {P+1}{\log _{2}17}}\right\rceil \,}</annotation>

</semantics>

</math><img src="./d7b9da88d478a5842f7aa9984da8e5a6aff674eb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:15.085ex; height:6.176ex;" alt="{\displaystyle \left\lceil \log _{2}{\frac {P+1}{\log _{2}17}}\right\rceil \,}" loading="lazy"> times // can be precomputed based on fixed P

X := X + X × (1 - D' × X)

end

return N' × X

</div>

For example, for a double-precision floating-point division, this method uses 10 multiplies, 9 adds, and 2 shifts.

<div class="mw-heading mw-heading4"><h4 id="Cubic_iteration">Cubic iteration</h4></div>

There is an iteration which uses three multiplications to cube the error:

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varepsilon _{i}=1-DX_{i}}</annotation>

</semantics>

</math><img src="./98115ffa92ddc012d5ca75557304758ab6693ee8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.633ex; height:2.509ex;" alt="{\displaystyle \varepsilon _{i}=1-DX_{i}}" loading="lazy"></dd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y_{i}=X_{i}\varepsilon _{i}}</annotation>

</semantics>

</math><img src="./9ecbe41aec52ae654ffaacd309e58de8de45e755.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.856ex; height:2.509ex;" alt="{\displaystyle Y_{i}=X_{i}\varepsilon _{i}}" loading="lazy"></dd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X_{i+1}=X_{i}+Y_{i}+Y_{i}\varepsilon _{i}.}</annotation>

</semantics>

</math><img src="./e174b9ec86837fab4a339f8968004e8eae0bc4cb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:23.158ex; height:2.509ex;" alt="{\displaystyle X_{i+1}=X_{i}+Y_{i}+Y_{i}\varepsilon _{i}.}" loading="lazy"></dd></dl>

The Yiεi term is new.

Expanding out the above, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X_{i+1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X_{i+1}}</annotation>

</semantics>

</math><img src="./4ec509c56b2912e5d86ebf632aa6bd987ffe6dc2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.824ex; height:2.509ex;" alt="{\displaystyle X_{i+1}}" loading="lazy"> can be written as

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msubsup>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}X_{i+1}&=X_{i}+X_{i}\varepsilon _{i}+X_{i}\varepsilon _{i}^{2}\\&=X_{i}+X_{i}(1-DX_{i})+X_{i}(1-DX_{i})^{2}\\&=3X_{i}-3DX_{i}^{2}+D^{2}X_{i}^{3},\end{aligned}}}</annotation>

</semantics>

</math><img src="./d03bd4503a0cde71ec8e467de2626497b8e4af99.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -4.338ex; width:44.502ex; height:9.843ex;" alt="{\displaystyle {\begin{aligned}X_{i+1}&=X_{i}+X_{i}\varepsilon _{i}+X_{i}\varepsilon _{i}^{2}\\&=X_{i}+X_{i}(1-DX_{i})+X_{i}(1-DX_{i})^{2}\\&=3X_{i}-3DX_{i}^{2}+D^{2}X_{i}^{3},\end{aligned}}}" loading="lazy"></dd></dl>

with the result that the error term

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msubsup>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msubsup>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mrow>

</msubsup>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}\varepsilon _{i+1}&=1-DX_{i+1}\\&=1-3DX_{i}+3D^{2}X_{i}^{2}-D^{3}X_{i}^{3}\\&=(1-DX_{i})^{3}\\&=\varepsilon _{i}^{3}.\end{aligned}}}</annotation>

</semantics>

</math><img src="./598ac23181733ee7b913b609e5784c6d15e0d267.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -5.672ex; margin-bottom: -0.333ex; width:36.55ex; height:13.009ex;" alt="{\displaystyle {\begin{aligned}\varepsilon _{i+1}&=1-DX_{i+1}\\&=1-3DX_{i}+3D^{2}X_{i}^{2}-D^{3}X_{i}^{3}\\&=(1-DX_{i})^{3}\\&=\varepsilon _{i}^{3}.\end{aligned}}}" loading="lazy"></dd></dl>

This is 3/2 the computation of the quadratic iteration, but achieves <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \log 3/\log 2\approx 1.585}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \log 3/\log 2\approx 1.585}</annotation>

</semantics>

</math><img src="./e8896bf86c7d49cfa79c8553089ec6bb64209e75.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.987ex; height:2.843ex;" alt="{\displaystyle \log 3/\log 2\approx 1.585}" loading="lazy"> as much convergence, so is slightly more efficient. Put another way, two iterations of this method raise the error to the ninth power at the same computational cost as three quadratic iterations, which only raise the error to the eighth power.

The number of correct bits after <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math><img src="./4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"> iterations is

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P=-3^{S}\log _{2}\varepsilon _{0}-1=3^{S}\log _{2}(1/\varepsilon _{0})-1}</annotation>

</semantics>

</math><img src="./ecd691dc0d645f4aa5b57169a032e4953dfcc181.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:40.289ex; height:3.176ex;" alt="{\displaystyle P=-3^{S}\log _{2}\varepsilon _{0}-1=3^{S}\log _{2}(1/\varepsilon _{0})-1}" loading="lazy"></dd></dl>

binary places. Typical values are:

<caption>Bits of reciprocal accuracy

</caption>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varepsilon _{0}}</annotation>

</semantics>

</math><img src="./acb0a8377db20e42274444cb181d51b5532b5844.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.138ex; height:2.009ex;" alt="{\displaystyle \varepsilon _{0}}" loading="lazy"></th>

<th colspan="4">Iterations

</th></tr>

<tr>

<th>3

</th></tr>

<tr>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1/17}</annotation>

</semantics>

</math><img src="./fddffd4792f3b4245b41d8f7e551d766cec12bd5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.65ex; height:2.843ex;" alt="{\displaystyle 1/17}" loading="lazy">

</th>

<td>3.09

</td>

<td>11.26

</td>

<td>35.79

</td>

<td>109.36

</td></tr>

<tr>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1/99}</annotation>

</semantics>

</math><img src="./450c9c8260e8f5f1f8d21bca139120eac9376ac8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.65ex; height:2.843ex;" alt="{\displaystyle 1/99}" loading="lazy">

</th>

<td>5.63

</td>

<td>18.89

</td>

<td>58.66

</td>

<td>177.99

</td></tr></tbody></table>

A quadratic initial estimate plus two cubic iterations provides ample precision for an IEEE double-precision result. It is also possible to use a mixture of quadratic and cubic iterations.

Using at least one quadratic iteration ensures that the error is positive, i.e. the reciprocal is underestimated.<a href="#cite_note-DigitalArithmetic-14">[13]</a>: 370 This can simplify a following rounding step if an exactly-rounded quotient is required.

Using higher degree polynomials in either the initialization or the iteration results in a degradation of performance because the extra multiplications required would be better spent on doing more iterations.

<div class="mw-heading mw-heading3"><h3 id="Goldschmidt_division">Goldschmidt division</h3></div>

Goldschmidt division<a href="#cite_note-15">[14]</a> (after Robert Elliott Goldschmidt)<a href="#cite_note-16">[15]</a> uses an iterative process of repeatedly multiplying both the dividend and divisor by a common factor Fi, chosen such that the divisor converges to 1. This causes the dividend to converge to the sought quotient Q:

<mfrac>

</mfrac>

</mrow>

<mfrac>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

<mfrac>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

<mfrac>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Q={\frac {N}{D}}{\frac {F_{1}}{F_{1}}}{\frac {F_{2}}{F_{2}}}{\frac {F_{\ldots }}{F_{\ldots }}}.}</annotation>

</semantics>

</math><img src="./cfafcb018d5743044f980e028fb504f6662d18cf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.171ex; width:19.742ex; height:5.509ex;" alt="{\displaystyle Q={\frac {N}{D}}{\frac {F_{1}}{F_{1}}}{\frac {F_{2}}{F_{2}}}{\frac {F_{\ldots }}{F_{\ldots }}}.}" loading="lazy"></dd></dl>

The steps for Goldschmidt division are:

<ol><li>Generate an estimate for the multiplication factor Fi .</li>

<li>Multiply the dividend and divisor by Fi .</li>

<li>If the divisor is sufficiently close to 1, return the dividend, otherwise, loop to step 1.</li></ol>

Assuming N/D has been scaled so that 0 < D < 1, each Fi is based on D:

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F_{i+1}=2-D_{i}.}</annotation>

</semantics>

</math><img src="./ae7d726be8caa19c6c7946ca355727b4f36cd716.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:14.867ex; height:2.509ex;" alt="{\displaystyle F_{i+1}=2-D_{i}.}" loading="lazy"></dd></dl>

Multiplying the dividend and divisor by the factor yields:

<mfrac>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

<mfrac>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

<mfrac>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {N_{i+1}}{D_{i+1}}}={\frac {N_{i}}{D_{i}}}{\frac {F_{i+1}}{F_{i+1}}}.}</annotation>

</semantics>

</math><img src="./5113b3bcd50f6ed41c54ddbf3f609c0d9f194e7e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:18.197ex; height:5.843ex;" alt="{\displaystyle {\frac {N_{i+1}}{D_{i+1}}}={\frac {N_{i}}{D_{i}}}{\frac {F_{i+1}}{F_{i+1}}}.}" loading="lazy"></dd></dl>

After a sufficient number k of iterations <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Q=N_{k}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Q=N_{k}}</annotation>

</semantics>

</math><img src="./4ca08ff8585045f19685c8a0c07755574942e0a5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.892ex; height:2.509ex;" alt="{\displaystyle Q=N_{k}}" loading="lazy">.

The Goldschmidt method is used in <a href="AMD" title="AMD">AMD</a> Athlon CPUs and later models.<a href="#cite_note-17">[16]</a><a href="#cite_note-18">[17]</a> It is also known as Anderson Earle Goldschmidt Powers (AEGP) algorithm and is implemented by various <a href="IBM" title="IBM">IBM</a> processors.<a href="#cite_note-19">[18]</a><a href="#cite_note-goldschmidt-analysis-20">[19]</a> Although it converges at the same rate as a Newton–Raphson implementation, one advantage of the Goldschmidt method is that the multiplications in the numerator and in the denominator can be done in parallel.<a href="#cite_note-goldschmidt-analysis-20">[19]</a>

<div class="mw-heading mw-heading4"><h4 id="Binomial_theorem">Binomial theorem</h4></div>

The Goldschmidt method can be used with factors that allow simplifications by the <a href="Binomial_theorem" title="Binomial theorem">binomial theorem</a>.

Assume ⁠<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N/D}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N/D}</annotation>

</semantics>

</math><img src="./d987c29f168f76b3ead5d019d1bd857a2126415c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.15ex; height:2.843ex;" alt="{\displaystyle N/D}" loading="lazy">⁠ has been scaled by a <a href="Power_of_two" title="Power of two">power of two</a> such that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D\in \left({\tfrac {1}{2}},1\right]}">

<mrow>

<mrow>

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D\in \left({\tfrac {1}{2}},1\right]}</annotation>

</semantics>

</math><img src="./01936269144731bcdf7908d2b23555ba00659675.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:10.654ex; height:3.509ex;" alt="{\displaystyle D\in \left({\tfrac {1}{2}},1\right]}" loading="lazy">.

We choose <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D=1-x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D=1-x}</annotation>

</semantics>

</math><img src="./67b31cf2fdf0edc1f9bc2dcff5ed74441df54d7f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:10.355ex; height:2.343ex;" alt="{\displaystyle D=1-x}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F_{i}=1+x^{2^{i}}}">

<msub>

</mrow>

</msub>

<msup>

<msup>

</mrow>

</msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F_{i}=1+x^{2^{i}}}</annotation>

</semantics>

</math><img src="./2a3077ff05d94fcfd311051c75a59abe42b92a25.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.404ex; height:3.343ex;" alt="{\displaystyle F_{i}=1+x^{2^{i}}}" loading="lazy">.

This yields

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

</mrow>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

</mfrac>

</mrow>

<msup>

</msup>

<mfrac>

<mrow>

<msup>

</msup>

<msup>

</mrow>

</msup>

<msup>

<msup>

</mrow>

</msup>

</mrow>

</msup>

</mrow>

<mrow>

<msup>

</msup>

<msup>

<msup>

</mrow>

</msup>

</mrow>

</msup>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {N}{1-x}}={\frac {N\cdot (1+x)}{1-x^{2}}}={\frac {N\cdot (1+x)\cdot (1+x^{2})}{1-x^{4}}}=\cdots =Q'={\frac {N'=N\cdot (1+x)\cdot (1+x^{2})\cdot \cdot \cdot (1+x^{2^{(n-1)}})}{D'=1-x^{2^{n}}\approx 1}}}</annotation>

</semantics>

</math>.</dd></dl>

After n steps <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left(x\in \left[0,{\tfrac {1}{2}}\right)\right)}">

<mrow>

<mrow>

<mrow>

<mrow>

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left(x\in \left[0,{\tfrac {1}{2}}\right)\right)}</annotation>

</semantics>

</math><img src="./66b01b704b7d733e103cdab6e00e694f5b9e1144.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:12.189ex; height:3.509ex;" alt="{\displaystyle \left(x\in \left[0,{\tfrac {1}{2}}\right)\right)}" loading="lazy">, the denominator <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1-x^{2^{n}}}">

<msup>

<msup>

</mrow>

</msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1-x^{2^{n}}}</annotation>

</semantics>

</math><img src="./809d9f3df6ebfa4fc488add34292fd6f65cbd6bf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:7.352ex; height:2.843ex;" alt="{\displaystyle 1-x^{2^{n}}}" loading="lazy"> can be rounded to 1 with a <a href="Relative_error" class="mw-redirect" title="Relative error">relative error</a>

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

<msup>

</msup>

<msup>

</msup>

</mrow>

<msup>

</msup>

</mfrac>

</mrow>

<msup>

<msup>

</mrow>

</msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varepsilon _{n}={\frac {Q'-N'}{Q'}}=x^{2^{n}}}</annotation>

</semantics>

</math><img src="./f6a73e13fb93fa34a0422da68ec10c3112bc7842.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:20.855ex; height:6.009ex;" alt="{\displaystyle \varepsilon _{n}={\frac {Q'-N'}{Q'}}=x^{2^{n}}}" loading="lazy"></dd></dl>

which is maximum at <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{-2^{n}}}">

<msup>

<msup>

</mrow>

</msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{-2^{n}}}</annotation>

</semantics>

</math><img src="./90d7061184ec120726609bfcbb3dad7dd1f9a57b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.46ex; height:2.676ex;" alt="{\displaystyle 2^{-2^{n}}}" loading="lazy"> when <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x={\tfrac {1}{2}}}">

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x={\tfrac {1}{2}}}</annotation>

</semantics>

</math><img src="./21bd3709df6bc6e0e3bcae866eede9d3d97f418c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:6.086ex; height:3.509ex;" alt="{\displaystyle x={\tfrac {1}{2}}}" loading="lazy">, thus providing a minimum precision of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{n}}</annotation>

</semantics>

</math><img src="./8226f30650ee4fe4e640c6d2798127e80e9c160d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.381ex; height:2.343ex;" alt="{\displaystyle 2^{n}}" loading="lazy"> binary digits.

<div class="mw-heading mw-heading2"><h2 id="Large-integer_methods">Large-integer methods</h2></div>

Methods designed for hardware implementation generally do not scale to integers with thousands or millions of decimal digits; these frequently occur, for example, in <a href="Modular_arithmetic" title="Modular arithmetic">modular</a> reductions in <a href="Cryptography" title="Cryptography">cryptography</a>. For these large integers, more efficient division algorithms transform the problem to use a small number of multiplications, which can then be done using an asymptotically efficient <a href="Multiplication_algorithm" title="Multiplication algorithm">multiplication algorithm</a> such as the <a href="Karatsuba_algorithm" title="Karatsuba algorithm">Karatsuba algorithm</a>, <a href="Toom%E2%80%93Cook_multiplication" title="Toom–Cook multiplication">Toom–Cook multiplication</a> or the <a href="Sch%C3%B6nhage%E2%80%93Strassen_algorithm" title="Schönhage–Strassen algorithm">Schönhage–Strassen algorithm</a>. The result is that the <a href="Computational_complexity" title="Computational complexity">computational complexity</a> of the division is of the same order (up to a multiplicative constant) as that of the multiplication. Examples include reduction to multiplication by <a href="Newton's_method" title="Newton's method">Newton's method</a> as <a href="#Newton–Raphson_division">described above</a>,<a href="#cite_note-21">[20]</a> as well as the slightly faster Burnikel-Ziegler division,<a href="#cite_note-22">[21]</a> <a href="Barrett_reduction" title="Barrett reduction">Barrett reduction</a> and <a href="Montgomery_reduction" class="mw-redirect" title="Montgomery reduction">Montgomery reduction</a> algorithms.<a href="#cite_note-23">[22]</a> Newton's method is particularly efficient in scenarios where one must divide by the same divisor many times, since after the initial Newton inversion only one (truncated) multiplication is needed for each division.

<div class="mw-heading mw-heading2"><h2 id="Division_by_a_constant">Division by a constant</h2></div>

The division by a constant D is equivalent to the multiplication by its <a href="Multiplicative_inverse" title="Multiplicative inverse">reciprocal</a>.

Since the denominator is constant, so is its reciprocal (1/D). Thus it is possible to compute the value of (1/D) once at compile time, and at run time perform the multiplication N·(1/D) rather than the division N/D. In <a href="Floating-point" class="mw-redirect" title="Floating-point">floating-point</a> arithmetic the use of (1/D) presents little problem,<a href="#cite_note-24">[a]</a> but in <a href="Integer_(computer_science)" title="Integer (computer science)">integer</a> arithmetic the reciprocal will always evaluate to zero (assuming |D| > 1).

It is not necessary to use specifically (1/D); any value (X/Y) that reduces to (1/D) may be used. For example, for division by 3, the factors 1/3, 2/6, 3/9, or 194/582 could be used. Consequently, if Y were a power of two the division step would reduce to a fast right bit shift. The effect of calculating N/D as (N·X)/Y replaces a division with a multiply and a shift. Note that the parentheses are important, as N·(X/Y) will evaluate to zero.

However, unless D itself is a power of two, there is no X and Y that satisfies the conditions above. Fortunately, (N·X)/Y gives exactly the same result as N/D in integer arithmetic even when (X/Y) is not exactly equal to 1/D, but "close enough" that the error introduced by the approximation is in the bits that are discarded by the shift operation.<a href="#cite_note-25">[23]</a><a href="#cite_note-26">[24]</a><a href="#cite_note-27">[25]</a> <a href="Barrett_reduction" title="Barrett reduction">Barrett reduction</a> uses powers of 2 for the value of Y to make division by Y a simple right shift.<a href="#cite_note-29">[b]</a>

As a concrete <a href="Fixed-point_arithmetic" title="Fixed-point arithmetic">fixed-point arithmetic</a> example, for 32-bit unsigned integers, division by 3 can be replaced with a multiply by <style data-mw-deduplicate="TemplateStyles:r1214402035">

/* start https://en.wikipedia.org/ */

.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}

/* end https://en.wikipedia.org/ */

</style>⁠2863311531/233⁠, a multiplication by 2863311531 (<a href="Hexadecimal" title="Hexadecimal">hexadecimal</a> 0xAAAAAAAB) followed by a 33 right bit shift. The value of 2863311531 is calculated as ⁠233/3⁠, then rounded up. Likewise, division by 10 can be expressed as a multiplication by 3435973837 (0xCCCCCCCD) followed by division by 235 (or 35 right bit shift).<a href="#cite_note-Hacker's_Delight-30">[27]</a>: p230-234 <a href="OEIS" class="mw-redirect" title="OEIS">OEIS</a> provides sequences of the constants for multiplication as <a href="https://oeis.org/A346495" class="extiw external" title="oeis:A346495">A346495</a> and for the right shift as <a href="https://oeis.org/A346496" class="extiw external" title="oeis:A346496">A346496</a>.

For general x-bit unsigned integer division where the divisor D is not a power of 2, the following identity converts the division into two x-bit addition/subtraction, one x-bit by x-bit multiplication (where only the upper half of the result is used) and several shifts, after precomputing <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k=x+\lceil \log _{2}{D}\rceil }">

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k=x+\lceil \log _{2}{D}\rceil }</annotation>

</semantics>

</math><img src="./9338c4c89623bd386dbe012c1357a2254506eb9f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.882ex; height:2.843ex;" alt="{\displaystyle k=x+\lceil \log _{2}{D}\rceil }" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a=\left\lceil {\frac {2^{k}}{D}}\right\rceil -2^{x}}">

<mrow>

<mfrac>

<msup>

</mrow>

</msup>

</mfrac>

</mrow>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a=\left\lceil {\frac {2^{k}}{D}}\right\rceil -2^{x}}</annotation>

</semantics>

</math><img src="./1698b05b8d70d452d2517ed9b8899fd8fb3d5d22.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:15.301ex; height:6.343ex;" alt="{\displaystyle a=\left\lceil {\frac {2^{k}}{D}}\right\rceil -2^{x}}" loading="lazy">:

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

<mrow>

<mfrac>

<mrow>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</mrow>

<msup>

</mrow>

</msup>

</mfrac>

</mrow>

</mrow>

<mtext> where </mtext>

</mrow>

<mrow>

<mfrac>

<mrow>

</mrow>

<msup>

</mrow>

</msup>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left\lfloor {\frac {N}{D}}\right\rfloor =\left\lfloor {\frac {\left\lfloor {\frac {N-b}{2}}\right\rfloor +b}{2^{k-x-1}}}\right\rfloor {\text{ where }}b=\left\lfloor {\frac {Na}{2^{x}}}\right\rfloor }</annotation>

</semantics>

</math><img src="./bfb5d8ba6fd1c53ffdfa6f2731779bf677b53be6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -4.505ex; width:41.649ex; height:10.176ex;" alt="{\displaystyle \left\lfloor {\frac {N}{D}}\right\rfloor =\left\lfloor {\frac {\left\lfloor {\frac {N-b}{2}}\right\rfloor +b}{2^{k-x-1}}}\right\rfloor {\text{ where }}b=\left\lfloor {\frac {Na}{2^{x}}}\right\rfloor }" loading="lazy"></dd></dl>

In some cases, division by a constant can be accomplished in even less time by converting the "multiply by a constant" into a <a href="Multiplication_algorithm#Shift_and_add" title="Multiplication algorithm">series of shifts and adds or subtracts</a>.<a href="#cite_note-31">[28]</a> Of particular interest is division by 10, for which the exact quotient is obtained, with remainder if required.<a href="#cite_note-32">[29]</a>

<div class="mw-heading mw-heading2"><h2 id="Rounding_error">Rounding error</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

When a division operation is performed, the exact <a href="Quotient" title="Quotient">quotient</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q}</annotation>

</semantics>

</math><img src="./06809d64fa7c817ffc7e323f85997f783dbdf71d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.07ex; height:2.009ex;" alt="{\displaystyle q}" loading="lazy"> and <a href="Remainder" title="Remainder">remainder</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r}</annotation>

</semantics>

</math><img src="./0d1ecb613aa2984f0576f70f86650b7c2a132538.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:1.676ex;" alt="{\displaystyle r}" loading="lazy"> are approximated to fit within the computer’s precision limits. The Division Algorithm states:

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [a=bq+r]}</annotation>

</semantics>

</math><img src="./082dbab89cb70659e15587e2aae1cbcb37f37dcc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.578ex; height:2.843ex;" alt="{\displaystyle [a=bq+r]}" loading="lazy">

where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0\leq r<|b|}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0\leq r<|b|}</annotation>

</semantics>

</math><img src="./d3fc64c6bf589852efd9096b83210cc89be7bdb2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.699ex; height:2.843ex;" alt="{\displaystyle 0\leq r<|b|}" loading="lazy">.

In <a href="Floating-point_arithmetic" title="Floating-point arithmetic">floating-point arithmetic</a>, the quotient <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q}</annotation>

</semantics>

</math><img src="./06809d64fa7c817ffc7e323f85997f783dbdf71d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.07ex; height:2.009ex;" alt="{\displaystyle q}" loading="lazy"> is represented as <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\tilde {q}}}">

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\tilde {q}}}</annotation>

</semantics>

</math><img src="./9799511dfd2e51ec2827f6cdab2b75ed8cd1595e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.377ex; height:2.509ex;" alt="{\displaystyle {\tilde {q}}}" loading="lazy"> and the remainder <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r}</annotation>

</semantics>

</math><img src="./0d1ecb613aa2984f0576f70f86650b7c2a132538.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:1.676ex;" alt="{\displaystyle r}" loading="lazy"> as <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\tilde {r}}}">

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\tilde {r}}}</annotation>

</semantics>

</math><img src="./85962e2c63f61329fa0089221292e8e519c9fe2c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.292ex; height:2.176ex;" alt="{\displaystyle {\tilde {r}}}" loading="lazy">, introducing <a href="Round-off_error" title="Round-off error">rounding errors</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \epsilon _{q}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \epsilon _{q}}</annotation>

</semantics>

</math><img src="./0f90289afd4033c580eea31973595ee8402ddb45.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:1.933ex; height:2.343ex;" alt="{\displaystyle \epsilon _{q}}" loading="lazy"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \epsilon _{q}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \epsilon _{q}}</annotation>

</semantics>

</math><img src="./0f90289afd4033c580eea31973595ee8402ddb45.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:1.933ex; height:2.343ex;" alt="{\displaystyle \epsilon _{q}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \epsilon _{r}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \epsilon _{r}}</annotation>

</semantics>

</math><img src="./7ff36e034ac43c6b67b68ed1b87ca7a5b4e42f9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.918ex; height:2.009ex;" alt="{\displaystyle \epsilon _{r}}" loading="lazy">:

<mover>

</mover>

</mrow>

<msub>

</mrow>

</msub>

<mover>

</mover>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [{\tilde {q}}=q+\epsilon _{q}][{\tilde {r}}=r+\epsilon _{r}]}</annotation>

</semantics>

</math><img src="./a8d5bc6d54afa2acff2eacc1355cb4dd75829038.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:23.103ex; height:3.009ex;" alt="{\displaystyle [{\tilde {q}}=q+\epsilon _{q}][{\tilde {r}}=r+\epsilon _{r}]}" loading="lazy">

This rounding causes a small error, which can propagate and accumulate through subsequent calculations. Such errors are particularly pronounced in iterative processes and when subtracting nearly equal values - is told <a href="Catastrophic_cancellation" title="Catastrophic cancellation">loss of significance</a>. To mitigate these errors, techniques such as the use of <a href="Guard_digit" title="Guard digit">guard digits</a> or higher precision arithmetic are employed.<a href="#cite_note-33">[30]</a><a href="#cite_note-34">[31]</a>

<div role="note" class="hatnote navigation-not-searchable">Further information: <a href="Floating_point" class="mw-redirect" title="Floating point">Floating point</a></div>

<ul><li><a href="Galley_division" title="Galley division">Galley division</a></li>

<li><a href="Multiplication_algorithm" title="Multiplication algorithm">Multiplication algorithm</a></li>

<li><a href="Pentium_FDIV_bug" title="Pentium FDIV bug">Pentium FDIV bug</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2></div>

<li id="cite_note-24"><a href="#cite_ref-24">^</a> Despite how "little" problem the optimization causes, this reciprocal optimization is still usually hidden behind a "fast math" flag in modern <a href="Compiler" title="Compiler">compilers</a> as it is inexact.

</li>

<li id="cite_note-29"><a href="#cite_ref-29">^</a> Modern <a href="Compilers" class="mw-redirect" title="Compilers">compilers</a> commonly perform this integer multiply-and-shift optimization; for a constant only known at run-time, however, the program must implement the optimization itself.<a href="#cite_note-28">[26]</a>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFRodeheffer2008" class="citation techreport cs1">Rodeheffer, Thomas L. (2008-08-26). <a rel="nofollow" class="external text" href="https://www.microsoft.com/en-us/research/wp-content/uploads/2008/08/tr-2008-141.pdf">Software Integer Division</a> (PDF) (Technical report). Microsoft Research, Silicon Valley.</cite>

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> <cite id="CITEREFMorrisIniewski2017" class="citation book cs1">Morris, James E.; Iniewski, Krzysztof (2017-11-22). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=wAhEDwAAQBAJ&q=restoring+division+fixed-point+fractional+numbers&pg=PA243">Nanoelectronic Device Applications Handbook</a>. CRC Press. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-351-83197-0</bdi>.</cite>

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> <cite id="CITEREFShaw1950" class="citation journal cs1">Shaw, Robert F. (1950). <a rel="nofollow" class="external text" href="http://aip.scitation.org/doi/10.1063/1.1745692">"Arithmetic Operations in a Binary Computer"</a>. Review of Scientific Instruments. 21 (8): 690. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/1950RScI...21..687S">1950RScI...21..687S</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1063%2F1.1745692">10.1063/1.1745692</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0034-6748">0034-6748</a>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20220228182241/https://aip.scitation.org/doi/10.1063/1.1745692">Archived</a> from the original on 2022-02-28. Retrieved 2022-02-28.</cite>

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> <cite id="CITEREFFlynn" class="citation web cs1">Flynn. <a rel="nofollow" class="external text" href="https://web.stanford.edu/class/ee486/doc/chap5.pdf">"Stanford EE486 (Advanced Computer Arithmetic Division) – Chapter 5 Handout (Division)"</a> (PDF). Stanford University. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20220418044630/http://web.stanford.edu/class/ee486/doc/chap5.pdf">Archived</a> (PDF) from the original on 2022-04-18. Retrieved 2019-06-24.</cite>

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> <cite id="CITEREFHarrisObermanHorowitz1998" class="citation techreport cs1">Harris, David L.; Oberman, Stuart F.; Horowitz, Mark A. (9 September 1998). <a rel="nofollow" class="external text" href="http://pages.hmc.edu/harris/research/srtlong.pdf">SRT Division: Architectures, Models, and Implementations</a> (PDF) (Technical report). Stanford University. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20161224030439/http://pages.hmc.edu/harris/research/srtlong.pdf">Archived</a> (PDF) from the original on 24 December 2016. Retrieved 23 December 2016.</cite>

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> <cite id="CITEREFMcCannPippenger2005" class="citation journal cs1">McCann, Mark; Pippenger, Nicholas (2005). <a rel="nofollow" class="external text" href="https://ieeexplore.ieee.org/document/614875">"SRT Division Algorithms as Dynamical Systems"</a>. SIAM Journal on Computing. 34 (6): 1279–1301. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.72.6993">10.1.1.72.6993</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2FS009753970444106X">10.1137/S009753970444106X</a>. <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/2429%2F12179">2429/12179</a>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20220824213238/https://ieeexplore.ieee.org/document/614875">Archived</a> from the original on 2022-08-24. Retrieved 2022-08-24.</cite>

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> <cite id="CITEREFCockeSweeney1957" class="citation cs2">Cocke, John; Sweeney, D.W. (11 February 1957), <a rel="nofollow" class="external text" href="https://www.computerhistory.org/collections/catalog/102632302">High speed arithmetic in a parallel device</a> (Company Memo), IBM, p. 20, <a rel="nofollow" class="external text" href="https://web.archive.org/web/20220824212341/https://www.computerhistory.org/collections/catalog/102632302">archived</a> from the original on 24 August 2022, retrieved 24 August 2022</cite><code class="cs1-code">{{citation}}</code>: CS1 maint: location missing publisher (link)

</li>

<li id="cite_note-9"><a href="#cite_ref-9">^</a> <cite id="CITEREFRobertson1958" class="citation journal cs1">Robertson, James (1958-09-01). <a rel="nofollow" class="external text" href="https://ieeexplore.ieee.org/document/5222579">"A New Class of Digital Division Methods"</a>. IRE Transactions on Electronic Computers. EC-7 (3). IEEE: 218–222. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTEC.1958.5222579">10.1109/TEC.1958.5222579</a>. <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/2027%2Fuiuo.ark%3A%2F13960%2Ft0gt7529c">2027/uiuo.ark:/13960/t0gt7529c</a>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20220824213239/https://ieeexplore.ieee.org/document/5222579">Archived</a> from the original on 2022-08-24. Retrieved 2022-08-24.</cite>

</li>

<li id="cite_note-10"><a href="#cite_ref-10">^</a> <cite id="CITEREFTocher1958" class="citation journal cs1">Tocher, K.D. (1958-01-01). <a rel="nofollow" class="external text" href="https://academic.oup.com/qjmam/article-abstract/11/3/364/1883426">"Techniques of Multiplication and Division for Automatic Binary Computers"</a>. The Quarterly Journal of Mechanics and Applied Mathematics. 11 (3): 364–384. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1093%2Fqjmam%2F11.3.364">10.1093/qjmam/11.3.364</a>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20220824214400/https://academic.oup.com/qjmam/article-abstract/11/3/364/1883426">Archived</a> from the original on 2022-08-24. Retrieved 2022-08-24.</cite>

</li>

<li id="cite_note-11"><a href="#cite_ref-11">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www.intel.com/support/processors/pentium/sb/cs-012997.htm">"Statistical Analysis of Floating Point Flaw"</a>. Intel Corporation. 1994. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20131023060231/http://www.intel.com/support/processors/pentium/sb/cs-012997.htm">Archived</a> from the original on 23 October 2013. Retrieved 22 October 2013.</cite>

</li>

<li id="cite_note-12"><a href="#cite_ref-12">^</a> <cite id="CITEREFObermanFlynn1995" class="citation techreport cs1">Oberman, Stuart F.; Flynn, Michael J. (July 1995). <a rel="nofollow" class="external text" href="http://i.stanford.edu/pub/cstr/reports/csl/tr/95/675/CSL-TR-95-675.pdf">An Analysis of Division Algorithms and Implementations</a> (PDF) (Technical report). Stanford University. CSL-TR-95-675. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20170517133304/http://i.stanford.edu/pub/cstr/reports/csl/tr/95/675/CSL-TR-95-675.pdf">Archived</a> (PDF) from the original on 2017-05-17. Retrieved 2016-12-23.</cite>

</li>

<li id="cite_note-13"><a href="#cite_ref-13">^</a> <cite id="CITEREFShirriff2024" class="citation web cs1">Shirriff, Ken (28 Dec 2024). <a rel="nofollow" class="external text" href="https://www.righto.com/2024/12/this-die-photo-of-pentium-shows.html">"Intel's $475 million error: the silicon behind the Pentium division bug"</a>. Righto. Retrieved 30 Dec 2024.</cite>

</li>

<li id="cite_note-DigitalArithmetic-14"><a href="#cite_ref-DigitalArithmetic_14-0">^</a> <cite id="CITEREFErcegovacLang2004" class="citation book cs1">Ercegovac, Miloš D.; Lang, Tomás (2004). "Chapter 7: Reciprocal. Division, Reciprocal Square Root, and Square Root by Iterative Approximation". Digital Arithmetic. Morgan Kaufmann. pp. 367–395. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>1-55860-798-6</bdi>.</cite>

</li>

<li id="cite_note-15"><a href="#cite_ref-15">^</a> <cite id="CITEREFGoldschmidt1964" class="citation thesis cs1">Goldschmidt, Robert E. (1964). <a rel="nofollow" class="external text" href="http://dspace.mit.edu/bitstream/handle/1721.1/11113/34136725-MIT.pdf">Applications of Division by Convergence</a> (PDF) (Thesis). M.Sc. dissertation. M.I.T. <a href="OCLC_(identifier)" class="mw-redirect" title="OCLC (identifier)">OCLC</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/oclc/34136725">34136725</a>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20151210223340/http://dspace.mit.edu/bitstream/handle/1721.1/11113/34136725-MIT.pdf">Archived</a> (PDF) from the original on 2015-12-10. Retrieved 2015-09-15.</cite>

</li>

<li id="cite_note-16"><a href="#cite_ref-16">^</a> <cite class="citation journal cs1"><a rel="nofollow" class="external text" href="https://web.archive.org/web/20180718114413/https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=5392026">"Authors"</a>. IBM Journal of Research and Development. 11: 125–127. 1967. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1147%2Frd.111.0125">10.1147/rd.111.0125</a>. Archived from <a rel="nofollow" class="external text" href="https://ieeexplore.ieee.org/document/5392026">the original</a> on 18 July 2018.</cite>

</li>

<li id="cite_note-17"><a href="#cite_ref-17">^</a> <cite id="CITEREFOberman1999" class="citation book cs1">Oberman, Stuart F. (1999). <a rel="nofollow" class="external text" href="http://www.acsel-lab.com/arithmetic/arith14/papers/ARITH14_Oberman.pdf">"Floating point division and square root algorithms and implementation in the AMD-K7 Microprocessor"</a> (PDF). Proceedings 14th IEEE Symposium on Computer Arithmetic (Cat. No.99CB36336). pp. 106–115. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FARITH.1999.762835">10.1109/ARITH.1999.762835</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-7695-0116-8</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:12793819">12793819</a>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20151129095846/http://www.acsel-lab.com/arithmetic/arith14/papers/ARITH14_Oberman.pdf">Archived</a> (PDF) from the original on 2015-11-29. Retrieved 2015-09-15.</cite>

</li>

<li id="cite_note-18"><a href="#cite_ref-18">^</a> <cite id="CITEREFSoderquistLeeser1997" class="citation journal cs1">Soderquist, Peter; Leeser, Miriam (July–August 1997). <a rel="nofollow" class="external text" href="https://www.researchgate.net/publication/2511700">"Division and Square Root: Choosing the Right Implementation"</a>. IEEE Micro. 17 (4): 56–66. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2F40.612224">10.1109/40.612224</a>.</cite>

</li>

<li id="cite_note-19"><a href="#cite_ref-19">^</a> S. F. Anderson, J. G. Earle, R. E. Goldschmidt, D. M. Powers. The IBM 360/370 model 91: floating-point execution unit, <a href="IBM_Journal_of_Research_and_Development" title="IBM Journal of Research and Development">IBM Journal of Research and Development</a>, January 1997

</li>

<li id="cite_note-goldschmidt-analysis-20">^ <a href="#cite_ref-goldschmidt-analysis_20-0">a</a> <a href="#cite_ref-goldschmidt-analysis_20-1">b</a> <cite id="CITEREFGuyPeterFerguson2005" class="citation journal cs1">Guy, Even; Peter, Siedel; Ferguson, Warren (1 February 2005). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.jcss.2004.08.004">"A parametric error analysis of Goldschmidt's division algorithm"</a>. Journal of Computer and System Sciences. 70 (1): 118–139. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.jcss.2004.08.004">10.1016/j.jcss.2004.08.004</a>.</cite>

</li>

<li id="cite_note-21"><a href="#cite_ref-21">^</a> <cite id="CITEREFHasselström2003" class="citation thesis cs1">Hasselström, Karl (2003). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20170708221722/https://static1.squarespace.com/static/5692a9ad7086d724272eb00a/t/5692dbe6b204d50df79e577f/1452465127528/masters-thesis.pdf">Fast Division of Large Integers: A Comparison of Algorithms</a> (PDF) (M.Sc. in Computer Science thesis). Royal Institute of Technology. Archived from <a rel="nofollow" class="external text" href="https://treskal.com/s/masters-thesis.pdf">the original</a> (PDF) on 8 July 2017. Retrieved 2017-07-08.</cite>

</li>

<li id="cite_note-22"><a href="#cite_ref-22">^</a> <cite id="CITEREFJoachim_Ziegler1998" class="citation cs2">Joachim Ziegler, Christoph Burnikel (1998), <a rel="nofollow" class="external text" href="https://domino.mpi-inf.mpg.de/internet/reports.nsf/efc044f1568a0058c125642e0064c817/a8cfefdd1ac031bbc125669b00493127/$FILE/MPI-I-98-1-022.ps">Fast Recursive Division</a>, Max-Planck-Institut für Informatik, <a rel="nofollow" class="external text" href="https://web.archive.org/web/20110426221250/http://domino.mpi-inf.mpg.de/internet/reports.nsf/efc044f1568a0058c125642e0064c817/a8cfefdd1ac031bbc125669b00493127/$FILE/MPI-I-98-1-022.ps">archived</a> from the original on 2011-04-26, retrieved 2021-09-10</cite><code class="cs1-code">{{citation}}</code>: CS1 maint: location missing publisher (link)

</li>

<li id="cite_note-23"><a href="#cite_ref-23">^</a> <cite id="CITEREFBarrett1987" class="citation conference cs1">Barrett, Paul (1987). <a rel="nofollow" class="external text" href="http://portal.acm.org/citation.cfm?id=36688">"Implementing the Rivest Shamir and Adleman public key encryption algorithm on a standard digital signal processor"</a>. Proceedings on Advances in cryptology---CRYPTO '86. London, UK: Springer-Verlag. pp. 311–323. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-387-18047-8</bdi>.</cite>

</li>

<li id="cite_note-25"><a href="#cite_ref-25">^</a> <cite id="CITEREFGranlundMontgomery1994" class="citation journal cs1">Granlund, Torbjörn; Montgomery, Peter L. (June 1994). <a rel="nofollow" class="external text" href="http://gmplib.org/~tege/divcnst-pldi94.pdf">"Division by Invariant Integers using Multiplication"</a> (PDF). SIGPLAN Notices. 29 (6): 61–72. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.1.2556">10.1.1.1.2556</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F773473.178249">10.1145/773473.178249</a>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20190606211506/https://gmplib.org/~tege/divcnst-pldi94.pdf">Archived</a> (PDF) from the original on 2019-06-06. Retrieved 2015-12-08.</cite>

</li>

<li id="cite_note-26"><a href="#cite_ref-26">^</a> <cite id="CITEREFMöllerGranlund2011" class="citation journal cs1">Möller, Niels; Granlund, Torbjörn (February 2011). <a rel="nofollow" class="external text" href="http://gmplib.org/~tege/division-paper.pdf">"Improved Division by Invariant Integers"</a> (PDF). IEEE Transactions on Computers. 60 (2): 165–175. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTC.2010.143">10.1109/TC.2010.143</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:13347152">13347152</a>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20151222160554/https://gmplib.org/~tege/division-paper.pdf">Archived</a> (PDF) from the original on 2015-12-22. Retrieved 2015-12-08.</cite>

</li>

<li id="cite_note-27"><a href="#cite_ref-27">^</a> ridiculous_fish.

<a rel="nofollow" class="external text" href="http://ridiculousfish.com/files/faster_unsigned_division_by_constants.pdf">"Labor of Division (Episode III): Faster Unsigned Division by Constants"</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20220108225258/http://ridiculousfish.com/files/faster_unsigned_division_by_constants.pdf">Archived</a> 2022-01-08 at the <a href="Wayback_Machine" title="Wayback Machine">Wayback Machine</a>.

2011.

</li>

<li id="cite_note-28"><a href="#cite_ref-28">^</a> <cite id="CITEREFridiculous_fish" class="citation web cs1">ridiculous_fish. <a rel="nofollow" class="external text" href="https://libdivide.com/">"libdivide, optimized integer division"</a>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20211123015446/https://libdivide.com/">Archived</a> from the original on 23 November 2021. Retrieved 6 July 2021.</cite>

</li>

<li id="cite_note-Hacker's_Delight-30"><a href="#cite_ref-Hacker's_Delight_30-0">^</a> <cite id="CITEREFWarren_Jr.2013" class="citation book cs1">Warren Jr., Henry S. (2013). <a href="Hacker's_Delight" title="Hacker's Delight">Hacker's Delight</a> (2 ed.). <a href="Addison_Wesley" class="mw-redirect" title="Addison Wesley">Addison Wesley</a> - <a href="Pearson_Education%2C_Inc." class="mw-redirect" title="Pearson Education, Inc.">Pearson Education, Inc.</a> <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-321-84268-8</bdi>.</cite>

</li>

<li id="cite_note-31"><a href="#cite_ref-31">^</a> LaBudde, Robert A.; Golovchenko, Nikolai; Newton, James; and Parker, David; <a rel="nofollow" class="external text" href="http://techref.massmind.org/techref/method/math/divconst.htm">Massmind: "Binary Division by a Constant"</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20220109215748/http://techref.massmind.org/techref/method/math/divconst.htm">Archived</a> 2022-01-09 at the <a href="Wayback_Machine" title="Wayback Machine">Wayback Machine</a>

</li>

<li id="cite_note-32"><a href="#cite_ref-32">^</a> <cite id="CITEREFVowels1992" class="citation journal cs1">Vowels, R. A. (1992). "Division by 10". Australian Computer Journal. 24 (3): 81–85.</cite>

</li>

<li id="cite_note-33"><a href="#cite_ref-33">^</a> <cite id="CITEREFL._Popyack2000" class="citation journal cs1">L. Popyack, Jeffrey (June 2000). <a rel="nofollow" class="external text" href="https://www.cs.drexel.edu/~popyack/Courses/CSP/Fa17/extras/Rounding/index.html">"Rounding Error"</a>. <a href="Drexel_University" title="Drexel University">Drexel University</a>.</cite>

</li>

<li id="cite_note-34"><a href="#cite_ref-34">^</a> <cite class="citation journal cs1"><a rel="nofollow" class="external text" href="https://lemesurierb.people.charleston.edu/elementary-numerical-analysis-python/notebooks/machine-numbers-rounding-error-and-error-propagation-python.html">"9. Machine Numbers, Rounding Error and Error Propagation"</a>. <a href="College_of_Charleston" title="College of Charleston">College of Charleston</a>. 8 February 2021.</cite>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2></div>

<ul><li><cite id="CITEREFSavard2018" class="citation web cs1">Savard, John J. G. (2018) [2006]. <a rel="nofollow" class="external text" href="http://www.quadibloc.com/comp/cp0202.htm">"Advanced Arithmetic Techniques"</a>. quadibloc. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20180703001722/http://www.quadibloc.com/comp/cp0202.htm">Archived</a> from the original on 2018-07-03. Retrieved 2018-07-16.</cite></li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Number-theoretic_algorithms413" style="padding:3px"><table class="nowraplinks mw-collapsible uncollapsed navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Number-theoretic_algorithms413" style="font-size:114%;margin:0 4em"><a href="Number_theory" title="Number theory">Number-theoretic</a> <a href="Algorithm" title="Algorithm">algorithms</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Primality_test" title="Primality test">Primality tests</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<li><a href="Baillie%E2%80%93PSW_primality_test" title="Baillie–PSW primality test">Baillie–PSW</a></li>

<li><a href="Elliptic_curve_primality" title="Elliptic curve primality">Elliptic curve</a></li>

<li><a href="Pocklington_primality_test" title="Pocklington primality test">Pocklington</a></li>

<li><a href="Fermat_primality_test" title="Fermat primality test">Fermat</a></li>

<li><a href="Lucas_primality_test" title="Lucas primality test">Lucas</a></li>

<li><a href="Lucas%E2%80%93Lehmer_primality_test" title="Lucas–Lehmer primality test">Lucas–Lehmer</a></li>

<li><a href="Lucas%E2%80%93Lehmer%E2%80%93Riesel_test" title="Lucas–Lehmer–Riesel test">Lucas–Lehmer–Riesel</a></li>

<li><a href="Proth's_theorem" title="Proth's theorem">Proth's theorem</a></li>

<li><a href="P%C3%A9pin's_test" title="Pépin's test">Pépin's</a></li>

<li><a href="Quadratic_Frobenius_test" title="Quadratic Frobenius test">Quadratic Frobenius</a></li>

<li><a href="Solovay%E2%80%93Strassen_primality_test" title="Solovay–Strassen primality test">Solovay–Strassen</a></li>

<li><a href="Miller%E2%80%93Rabin_primality_test" title="Miller–Rabin primality test">Miller–Rabin</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Generating_primes" class="mw-redirect" title="Generating primes">Prime-generating</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Sieve_of_Atkin" title="Sieve of Atkin">Sieve of Atkin</a></li>

<li><a href="Sieve_of_Eratosthenes" title="Sieve of Eratosthenes">Sieve of Eratosthenes</a></li>

<li><a href="Sieve_of_Pritchard" title="Sieve of Pritchard">Sieve of Pritchard</a></li>

<li><a href="Sieve_of_Sundaram" title="Sieve of Sundaram">Sieve of Sundaram</a></li>

<li><a href="Wheel_factorization" title="Wheel factorization">Wheel factorization</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Integer_factorization" title="Integer factorization">Integer factorization</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Continued_fraction_factorization" title="Continued fraction factorization">Continued fraction (CFRAC)</a></li>

<li><a href="Dixon's_factorization_method" title="Dixon's factorization method">Dixon's</a></li>

<li><a href="Lenstra_elliptic-curve_factorization" title="Lenstra elliptic-curve factorization">Lenstra elliptic curve (ECM)</a></li>

<li><a href="Euler's_factorization_method" title="Euler's factorization method">Euler's</a></li>

<li><a href="Pollard's_rho_algorithm" title="Pollard's rho algorithm">Pollard's rho</a></li>

<li><a href="Quadratic_sieve" title="Quadratic sieve">Quadratic sieve (QS)</a></li>

<li><a href="General_number_field_sieve" title="General number field sieve">General number field sieve (GNFS)</a></li>

<li><a href="Special_number_field_sieve" title="Special number field sieve">Special number field sieve (SNFS)</a></li>

<li><a href="Rational_sieve" title="Rational sieve">Rational sieve</a></li>

<li><a href="Fermat's_factorization_method" title="Fermat's factorization method">Fermat's</a></li>

<li><a href="Shanks's_square_forms_factorization" title="Shanks's square forms factorization">Shanks's square forms</a></li>

<li><a href="Trial_division" title="Trial division">Trial division</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Multiplication_algorithm" title="Multiplication algorithm">Multiplication</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Ancient_Egyptian_multiplication" title="Ancient Egyptian multiplication">Ancient Egyptian</a></li>

<li><a href="Karatsuba_algorithm" title="Karatsuba algorithm">Karatsuba</a></li>

<li><a href="Sch%C3%B6nhage%E2%80%93Strassen_algorithm" title="Schönhage–Strassen algorithm">Schönhage–Strassen</a></li>

<li><a href="F%C3%BCrer's_algorithm" class="mw-redirect" title="Fürer's algorithm">Fürer's</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Euclidean_division" title="Euclidean division">Euclidean</a> </th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Binary_division" class="mw-redirect" title="Binary division">Binary</a></li>

<li><a href="Chunking_(division)" title="Chunking (division)">Chunking</a></li>

<li><a href="Fourier_division" title="Fourier division">Fourier</a></li>

<li><a href="Goldschmidt_division" class="mw-redirect" title="Goldschmidt division">Goldschmidt</a></li>

<li><a href="Newton%E2%80%93Raphson_division" class="mw-redirect" title="Newton–Raphson division">Newton-Raphson</a></li>

<li><a href="Short_division" title="Short division">Short</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Discrete_logarithm" title="Discrete logarithm">Discrete logarithm</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Baby-step_giant-step" title="Baby-step giant-step">Baby-step giant-step</a></li>

<li><a href="Pollard's_rho_algorithm_for_logarithms" title="Pollard's rho algorithm for logarithms">Pollard rho</a></li>

<li><a href="Pollard's_kangaroo_algorithm" title="Pollard's kangaroo algorithm">Pollard kangaroo</a></li>

<li><a href="Pohlig%E2%80%93Hellman_algorithm" title="Pohlig–Hellman algorithm">Pohlig–Hellman</a></li>

<li><a href="Index_calculus_algorithm" title="Index calculus algorithm">Index calculus</a></li>

<li><a href="Function_field_sieve" title="Function field sieve">Function field sieve</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Greatest_common_divisor" title="Greatest common divisor">Greatest common divisor</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Binary_GCD_algorithm" title="Binary GCD algorithm">Binary</a></li>

<li><a href="Euclidean_algorithm" title="Euclidean algorithm">Euclidean</a></li>

<li><a href="Extended_Euclidean_algorithm" title="Extended Euclidean algorithm">Extended Euclidean</a></li>

<li><a href="Lehmer's_GCD_algorithm" title="Lehmer's GCD algorithm">Lehmer's</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Quadratic_residue" title="Quadratic residue">Modular square root</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Cipolla's_algorithm" title="Cipolla's algorithm">Cipolla</a></li>

<li><a href="Pocklington's_algorithm" title="Pocklington's algorithm">Pocklington's</a></li>

<li><a href="Tonelli%E2%80%93Shanks_algorithm" title="Tonelli–Shanks algorithm">Tonelli–Shanks</a></li>

<li><a href="Berlekamp%E2%80%93Rabin_algorithm" title="Berlekamp–Rabin algorithm">Berlekamp</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other algorithms</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Chakravala_method" title="Chakravala method">Chakravala</a></li>

<li><a href="Cornacchia's_algorithm" title="Cornacchia's algorithm">Cornacchia</a></li>

<li><a href="Exponentiation_by_squaring" title="Exponentiation by squaring">Exponentiation by squaring</a></li>

<li><a href="Integer_square_root" title="Integer square root">Integer square root</a></li>

<li><a href="Integer_relation_algorithm" title="Integer relation algorithm">Integer relation</a> (<a href="Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm" title="Lenstra–Lenstra–Lovász lattice basis reduction algorithm">LLL</a>; <a href="Korkine%E2%80%93Zolotarev_lattice_basis_reduction_algorithm" title="Korkine–Zolotarev lattice basis reduction algorithm">KZ</a>)</li>

<li><a href="Modular_exponentiation" title="Modular exponentiation">Modular exponentiation</a></li>

<li><a href="Montgomery_reduction" class="mw-redirect" title="Montgomery reduction">Montgomery reduction</a></li>

<li><a href="Schoof's_algorithm" title="Schoof's algorithm">Schoof</a></li>

<li><a href="Trachtenberg_system" title="Trachtenberg system">Trachtenberg system</a></li></ul>

</div></td></tr><tr><td class="navbox-abovebelow hlist" colspan="2"><div>

<ul><li>Italics indicate that algorithm is for numbers of special forms</li></ul>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-16" href="https://en.wikipedia.org/wiki/?title=Division_algorithm&oldid=1300744090">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>